// -*- mode: C++ ; compile-command: "g++ -I.. -g -O2 -c index.cc" -*-
/*
 *  Copyright (C) 2000,2014 B. Parisse, Institut Fourier, 38402 St Martin d'Heres
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program. If not, see <http://www.gnu.org/licenses/>.
 */
#if !defined _CASPP_MODELS_INDEX_H_
#define _CASPP_MODELS_INDEX_H_

#include <caspp/config.h>
#include <iostream>
#include <string>
#include "models/t_vector.h"

//////////////////////////////////////////
/// this commented and the old put back due to build issues... temporary change to get build going
//#if defined(VISUALC) && !defined(ConnectivityKit)
////##pragma anon_unions
//#endif
//========================================
#ifndef ConnectivityKit
#   ifndef _MSC_VER
//##pragma anon_unions
#   endif
#endif
///////////////////////////////////////////
#if defined UNORDERED_MAP && !defined(__APPLE__) && !defined(__clang__) && !defined(VISUALC)
#   include <tr1/unordered_map>
#   define HASH_MAP_NAMESPACE std::tr1
#   define hash_map unordered_map
#else // UNORDERED_MAP
#   if (defined(VISUALC) || defined(BESTA_OS))
#       undef HASH_MAP
#       undef EXT_HASH_MAP
#   endif
#   ifdef HASH_MAP
#       include <hash_map>
#       ifndef HASH_MAP_NAMESPACE
#           ifndef VISUALC
#               define HASH_MAP_NAMESPACE std
#           endif // VISUALC
#       endif // HASH_MAP_NAMESPACE
#   endif
#   ifdef EXT_HASH_MAP
#       include <ext/hash_map>
#       ifndef HASH_MAP_NAMESPACE
#           define HASH_MAP_NAMESPACE __gnu_cxx
#       endif
#   endif
#endif // UNORDERED_MAP

CASPP_NS_BEGIN

typedef int16_t Degree; // was short int

class Degree_v: public std::vector<Degree> {
public:
    typedef std::vector<Degree> __super;
    typedef Degree_v __self;
    Degree_v():
        __super() {};
    Degree_v(size_type i):
        __super(i) {};
    Degree_v(size_type i,const_reference d):
        __super(i,d) {};
    Degree_v(const_iterator & b, const_iterator & e)
        : __super(b,e) {}
    void dbgprint() {
#if 0
#ifndef NSPIRE
        CERR << *this << std::endl;
#endif
#endif
    }
};

CASPP_NS_END

CASPP_NS_BEGIN

Degree_v index_gcd(const Degree_v & a,const Degree_v & b);
Degree_v index_lcm(const Degree_v & a,const Degree_v & b);
CASPP_INLINE Degree_v Indexin(const Degree_v & a,const Degree_v & b) {
    return index_gcd(a,b);
}
CASPP_INLINE Degree_v Indexax(const Degree_v & a,const Degree_v & b) {
    return index_lcm(a,b);
}
void dbgprint(const Degree_v & i);
std::string print_INT_(int i);
std::string hexa_print_INT_(int i);
std::string octal_print_INT_(int i);
std::string binary_print_INT_(int i);
std::string print_INT_(const int_v & v);
std::string print_INT_(const std::vector<short int> & v);

Degree_v mergeindex(const Degree_v & i,const Degree_v & j);
// permutation inverse
int_v inverse(const int_v & p);
// transposition
int_v transposition(int i,int j,int size);
bool has(const Degree_v & p,int r);
// zero?
bool is_zero(const Degree_v & p);

bool lex_is_strictly_greater_Degree(const Degree_v & v1, const Degree_v & v2);

//*****************************************
// class for memory efficient indices
//*****************************************

class DegreeWrap: public Wrap {
public:
    Degree_v i;
    DegreeWrap()
        : Wrap() {}
    DegreeWrap(int s)
        : Wrap(),i(s) {}
    DegreeWrap(const Degree_v & I): Wrap(),i(I) {}
    DegreeWrap(Degree_v::const_iterator it,Degree_v::const_iterator itend)
        : Wrap(),i(it,itend) {}
};

// direct access to Degree in Index
const int POLY_VARS_DIRECT=sizeof(DegreeWrap *)/sizeof(Degree);
// HAS_POL_VARS_OTHER defines the number of word (pointer size) for
// other Degree directly encoded. Comment if none
#define HAS_POL_VARS_OTHER 1
#if HAS_POL_VARS_OTHER
const int POLY_VARS_OTHER=HAS_POL_VARS_OTHER*POLY_VARS_DIRECT;
#else
const int POLY_VARS_OTHER=0;
#endif
// capacity of Degree by direct addressing
const int POLY_VARS=POLY_VARS_DIRECT+POLY_VARS_OTHER-1;

#if defined(CASPP_NO_OPTIMIZATIONS) || ((defined(VISUALC) || defined(__APPLE__)) && !defined(CASPP_VECTOR))

class Index {
public:
    typedef Index __self;
    DegreeWrap * r_p;
    // construct
    Index(const Index & i) {
        r_p->retain();
        r_p=i.r_p;
    }
    Index(const Degree_v & i) {
        r_p=new DegreeWrap(i);
    }
    Index() {
        r_p=new DegreeWrap;
    }
    Index(size_t s) {
        r_p=new DegreeWrap(s);
    }
    Index(Degree_v::const_iterator it,Degree_v::const_iterator itend) {
        r_p=new DegreeWrap(it,itend);
    }
    // delete
    ~Index() {
        r_p->release();
        if (r_p->shouldDelete()) {
            delete r_p;
            r_p = 0;
        }
    }
    // copy
    const Index & operator = (const Index & other) {
        r_p->release();
        if (r_p->shouldDelete())
            delete r_p;
        r_p=other.r_p;
        r_p->retain();
        return *this;
    }
    
    // members
    Degree_v iref() const {
        return r_p->i;
    }
    Degree_v::iterator begin() {
        return r_p->i.begin();
    }
    Degree_v::iterator end() {
        return r_p->i.end();
    }
    Degree_v::reverse_iterator rbegin() {
        return r_p->i.rbegin();
    }
    Degree_v::reverse_iterator rend() {
        return r_p->i.rend();
    }
    Degree_v::const_iterator begin() const {
        return r_p->i.begin();
    }
    Degree_v::const_iterator end() const {
        return r_p->i.end();
    }
    Degree_v::const_reverse_iterator rbegin() const {
        return r_p->i.rbegin();
    }
    Degree_v::const_reverse_iterator rend() const {
        return r_p->i.rend();
    }
    Degree & front() {
        return *begin();
    }
    Degree front() const {
        return *begin();
    }
    Degree & back() {
        return *(end()-1);
    }
    Degree back() const {
        return *(end()-1);
    }
    Degree & operator [] (size_t pos) {
        return *(begin()+pos);
    }
    Degree operator [] (size_t pos) const {
        return *(begin()+pos);
    }
    void clear() {
        r_p->i.clear();
    }
    void reserve(size_t n) {
        r_p->i.reserve(n);
    }
    void push_back(Degree x) {
        r_p->i.push_back(x);
    }
    size_t size() const {
        return r_p->i.size();
    }
    bool is_zero() const ;
    size_t total_degree() const ;
    friend std::ostream & operator << (std::ostream & os, const Index & m ) {
        os << ":Index:[ " ;
        for (Degree_v::const_iterator it=m.begin();it!=m.end();++it)
            os << *it << " ";
        os << "] " ;
        return(os);
    }
    void dbgprint() const {
        COUT << *this << std::endl;
    }
    // set first index element to 0
    Index set_first_zero() const {
        Degree_v i(r_p->i); i[0]=0; return i;
    }
};

#else // VISUALC

class Index {
public:
    union {
        DegreeWrap * r_p;
        struct {
            Degree taille;
            Degree direct[POLY_VARS_DIRECT-1];
        };
    };
#ifdef HAS_POL_VARS_OTHER
    Degree other[POLY_VARS_OTHER];
#endif
    // construct
    Index(const Index & im) {
        if ( im.taille % 2) {
            * (unsigned long *) & taille = * (unsigned long *) &im.taille;
#if (HAS_POL_VARS_OTHER==1)
            * (unsigned long *) other = * (unsigned long *) im.other;
#endif
#if (HAS_POL_VARS_OTHER==2)
            * (unsigned long *) other = * (unsigned long *) im.other;
            * (((unsigned long *) other)+1) = * (((unsigned long *) im.other)+1);
#endif
#if (HAS_POL_VARS_OTHER>2)
            unsigned long * target = (unsigned long *) other, * end = target + POLY_VARS_OTHER/(sizeof(unsigned long)/sizeof(Degree));
            const unsigned long * source = (unsigned long *) im.other;
            for (;target!=end;++target,++source)
                *target=*source;
#endif
        } else {
            r_p=im.r_p;
            ++r_p->ref_count;
        }
    }
    Index(const Degree_v & i) {
        int s=i.size();
        if (s<=POLY_VARS) {
            taille=2*s+1;
            Degree * target=direct,*end=direct+s;
            Degree_v::const_iterator source=i.begin();
            for (;target!=end;++source,++target) {
                *target=*source;
            }
        } else {
            // taille = 0;
            r_p=new DegreeWrap(i);
        }
    }
    Index() {
        taille =1;
    }
    Index(size_t s) {
        if (int(s)<=POLY_VARS) {
            r_p=0;
            taille=2*s+1;
#if (HAS_POL_VARS_OTHER==1)
            * (unsigned long *) other =0;
#endif
#if (HAS_POL_VARS_OTHER==2)
            * (unsigned long *) other =0;
            * (((unsigned long *) other)+1) =0;
#endif
#if (HAS_POL_VARS_OTHER>2)
            unsigned long * target = (unsigned long *) other ;
            unsigned long * end = target + POLY_VARS_OTHER/(sizeof(unsigned long)/sizeof(Degree));
            for (;target!=end;++target)
                *target = 0;
#endif
        } else {
            // taille=0;
            r_p=new DegreeWrap(s);
        }
    }
    Index(Degree_v::const_iterator it,Degree_v::const_iterator itend) {
        if (itend-it<=POLY_VARS) {
            taille=2*(itend-it)+1;
            Degree * target = direct;
            for (;it!=itend;++it,++target) {
                *target=*it;
            }
        } else {
            // taille=0;
            r_p=new DegreeWrap(it,itend);
        }
    }
    // ptr[0] must be 2*size+1
    Index(Degree * ptr) {
        /*
#ifdef CASPP_DEBUG_SUPPORT
      if _p[0]/2>POLY_VARS)
    setsizeerr("Error index.h, size too large for direct access");
#endif
      */
        unsigned long * source = (unsigned long *) ptr;
        *(unsigned long *) &taille = *(unsigned long *) source;
#if (HAS_POL_VARS_OTHER==1)
        ++source;
        * (unsigned long *) other = *source;
#endif
#if (HAS_POL_VARS_OTHER==2)
        ++source;
        * (unsigned long *) other = *source;
        ++source;
        * (((unsigned long *) other)+1) = *source;
#endif
#if (HAS_POL_VARS_OTHER>2)
        unsigned long * target = (unsigned long *) other ;
        unsigned long * end = target + POLY_VARS_OTHER/(sizeof(unsigned long)/sizeof(Degree));
        for (++source;target!=end;++source,++target)
            *target = *source;
#endif
    }
    // delete
    ~Index() {
        if ( (taille % 2) == 0) {
            --r_p->ref_count;
            if (!r_p->ref_count)
                delete r_p;
        }
    }
    // copy
    const Index & operator = (const Index & other) {
        if ( (taille % 2) == 0) {
            --r_p->ref_count;
            if (!r_p->ref_count)
                delete r_p;
        }
        if ( (other.taille % 2) == 0) {
            r_p=other.r_p;
            ++r_p->ref_count;
        } else {
            * (unsigned long *) &taille = * (unsigned long *) &other.taille;
#if (HAS_POL_VARS_OTHER==1)
            * (unsigned long *) this->other = * (unsigned long *) other.other;
#endif
#if (HAS_POL_VARS_OTHER==2)
            * (unsigned long *) this->other = * (unsigned long *) other.other;
            * (((unsigned long *) this->other)+1) = * (((unsigned long *) other.other)+1);
#endif
#if (HAS_POL_VARS_OTHER>2)
            const unsigned long * source = (unsigned long * ) other.other;
            unsigned long * target = (unsigned long *) this->other;
            unsigned long * end = target + POLY_VARS_OTHER/(sizeof(unsigned long)/sizeof(Degree));
            for (;target!=end;++source,++target)
                * target = * source;
#endif
        }
        return *this;
    }
    
    // members
    Degree_v iref() const ;
    Degree_v::iterator begin() ;
    Degree_v::iterator end() ;
    Degree_v::const_iterator begin() const;
    Degree_v::const_iterator end() const;
    Degree & front() {
        return *begin();
    }
    Degree front() const {
        return *begin();
    }
    Degree & back() {
        return *(end()-1);
    }
    Degree back() const {
        return *(end()-1);
    }
    Degree & operator [] (size_t pos) {
        return *(begin()+pos);
    }
    Degree operator [] (size_t pos) const {
        return *(begin()+pos);
    }
    void clear() ;
    void reserve(size_t n);
    void push_back(Degree x);
    size_t size() const ;
    bool is_zero() const ;
    size_t total_degree() const ;
#ifdef NSPIRE
    template<class T> friend nio::ios_base<T> & operator << (nio::ios_base<T> & os,const Index & m ) {
        os << ":Index:[ " ;
        for (Degree_v::const_iterator it=m.begin();it!=m.end();++it)
            os << *it << " ";
        os << "] " ;
        return(os);
    }
#else
    friend std::ostream & operator << (std::ostream & os, const Index & m ) {
        os << ":Index:[ " ;
        for (Degree_v::const_iterator it=m.begin();it!=m.end();++it)
            os << *it << " ";
        os << "] " ;
        return(os);
    }
#endif
    void dbgprint() const {
        COUT << *this << std::endl;
    }
    // set first index element to 0
    Index set_first_zero() const;
};
#endif // VISUALC

#ifdef USTL
namespace ustl {
CASPP_INLINE bool operator > (const ::caspp::Degree_v & a,const ::caspp::Degree_v & b);
CASPP_INLINE bool operator < (const ::caspp::Degree_v & a,const ::caspp::Degree_v & b);
} // namespace USTL
#endif

// index type for tensors

Degree_v operator + (const Degree_v & a, const Degree_v & b);
Degree_v operator - (const Degree_v & a, const Degree_v & b);
Degree_v operator | (const Degree_v & a, const Degree_v & b);
Degree_v operator - (const Degree_v & a);
Degree_v operator * (const Degree_v & a, int fois);
CASPP_INLINE Degree_v operator * (int fois,const Degree_v & a) {
    return a*fois;
}
Degree_v operator / (const Degree_v & a, int divisepar);
int operator / (const Degree_v & a, const Degree_v & b);
// >= and <= are *partial* ordering on Degree_v
// they return TRUE if and only if >= or <= is true for *all* coordinates
bool all_sup_equal (const Degree_v & a, const Degree_v & b);
CASPP_INLINE bool operator >= (const Degree_v & a, const Degree_v & b) {
    return all_sup_equal(a,b);
}
bool all_inf_equal (const Degree_v & a, const Degree_v & b);
CASPP_INLINE bool operator <= (const Degree_v & a, const Degree_v & b) {
    return all_inf_equal(a,b);
}

Index operator + (const Index & a, const Index & b);
Index operator - (const Index & a, const Index & b);
Index operator * (const Index & a, int fois);
CASPP_INLINE Index operator * (int fois,const Index & a) {
    return a*fois;
}
Index operator / (const Index & a, int divisepar);
CASPP_INLINE int operator / (const Index & a,const Index & b) {
    return a.iref() / b.iref();
}
bool operator == (const Index & i1, const Index & i2);
bool operator != (const Index & i1, const Index & i2);
bool operator >= (const Index & a, const Index & b);
bool operator <= (const Index & a, const Index & b);

#ifdef HASH_MAP_NAMESPACE
CASPP_INLINE size_t index_hash_function(const Degree_v & v) {
    Degree_v::const_iterator it=v.begin(),itend=v.end();
    size_t res=0;
    if (itend-it>16)
        itend=it+16;
    if (itend-it>8) {
        for (;it!=itend;++it)
            res = (res << 2) | *it;
    } else {
        for (;it!=itend;++it)
            res = (res << 4) | *it;
    }
    return res;
}

/*
  CASPP_INLINE size_t index_hash_function(const vector<int> & v) {
    vector<int>::const_iterator it=v.begin(),itend=v.end();
    if (itend-it>16)
      itend=it+16;
    size_t res=0,decal=32/(itend-it);
    for (;;) {
      --itend;
      res = (res << decal) | *itend;
      if (itend==it)
    return res;
    }
  }
  */

class hash_function_object {
public:
    size_t operator () (const Degree_v & v) const {
        return index_hash_function(v);
    }
    hash_function_object() {};
};

typedef HASH_MAP_NAMESPACE::hash_map< Degree_v,Index,hash_function_object > hash_index ;

// extern std::vector<hash_index> config.hash_index;

#endif

int sum_degree(const Index & v1);
CASPP_INLINE int total_degree(const Index & v1) {
    return sum_degree(v1);
}
bool i_lex_is_greater(const Index & v1, const Index & v2);
bool i_lex_is_strictly_greater(const Index & v1, const Index & v2);
bool i_total_revlex_is_greater(const Index & v1, const Index & v2);
bool i_total_revlex_is_strictly_greater(const Index & v1, const Index & v2);
bool i_total_lex_is_greater(const Index & v1, const Index & v2);
bool i_total_lex_is_strictly_greater(const Index & v1, const Index & v2);
bool i_11var_is_greater(const Index & v1, const Index & v2);
bool i_7var_is_greater(const Index & v1, const Index & v2);
bool i_3var_is_greater(const Index & v1, const Index & v2);
CASPP_INLINE bool i_11var_is_strictly_greater(const Index & v1, const Index & v2) {
    return !i_11var_is_greater(v2,v1);
}
CASPP_INLINE bool i_7var_is_strictly_greater(const Index & v1, const Index & v2) {
    return !i_7var_is_greater(v2,v1);
}
CASPP_INLINE bool i_3var_is_strictly_greater(const Index & v1, const Index & v2) {
    return !i_3var_is_greater(v2,v1);
}

void index_lcm(const Index & a,const Index & b,Degree_v & res);
bool disjoint(const Index & a,const Index & b);

CASPP_NS_END

#if 0 // def NSPIRE
namespace std {
CASPP_INLINE bool operator > (const caspp::Degree_v & a,const caspp::Degree_v & b) {
    if (a.size()!=b.size())
        return a.size()>b.size();
    return !caspp::all_inf_equal(a,b);
}
CASPP_INLINE bool operator < (const caspp::Degree_v & a,const caspp::Degree_v & b) {
    if (a.size()!=b.size())
        return a.size()<b.size();
    return !caspp::all_sup_equal(a,b);
}
} // namespace std
#endif

#endif // ndef _CASPP_MODELS_INDEX_H_
